package leetcode_core.leetcode_6;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年02月13日 22:17
 */
public class LargestRectangleArea {
    public int largestRectangleArea(int[] nums) {
        //采用单调栈算法解决问题
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        //在首位部分分别添加0,使得其能够强制弹出元素
        int[] heights = new int[n+2];
        Stack<Integer> stack = new Stack<>();
        System.arraycopy(nums, 1, heights, 1, n - 1);
        int res = -1;
        for(int i = 0;i<n+2;i++){
            while(!stack.isEmpty() && stack.peek() > heights[i]){
                Integer top = stack.pop();
                int right = i;
                int left = stack.peek();
                res = Math.max(res,(right-left-1)*heights[top]);
            }
            stack.push(i);
        }
        return res;
    }
}
